package codeTop;

/**
 * q572
 *
 * @author 雨凡
 * @version q572.java, v0.1
 * @date 2025/07/02/12:44
 */
public class q572 {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (subRoot == null) {
            return true;
        }
        dfs(root,subRoot);
        return flag;
    }
    boolean flag = false;

    private void dfs(TreeNode root, TreeNode subRoot) {
        if (flag) {
            return;
        }
        if (root == null) {
            return;
        }
        if (root.val == subRoot.val) {
            if (isSame(root, subRoot)) {
                flag = true;
                return;
            }
        }
        dfs(root.left,subRoot);
        dfs(root.right,subRoot);
    }

    private boolean isSame(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root != null && subRoot != null) {
            if (root.val == subRoot.val) {
                return isSame(root.left,subRoot.left)&&isSame(root.right,subRoot.right);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        q572 q = new q572();
        TreeNode root = new TreeNode(3, new TreeNode(4, new TreeNode(1), new TreeNode(2, new TreeNode(0), null)), new TreeNode(5));
        TreeNode subRoot = new TreeNode(4, new TreeNode(1), new TreeNode(2));
        System.out.println(q.isSubtree(root, subRoot));
    }
}
